2516. 每种字符至少取 K 个

Similar Question

Solution Tips

方案一: 反向思维 + 滑动窗口

var takeCharacters = function (s, k) {
    // 滑动窗口, 窗口的特征是 内部的 a b c 至少大于等于 k 个
    // 可以从左侧取, 可以从右侧取, 无法确定怎么取才是最优的
    // 反向思维的话就是统计 s 的字符数, 要让 window 里的字符数全部少于等于 charCount - k
    // window 最大的时候, 剩余的就最少, 最符合题意, 还是反向思维好理解哇
    if (k === 0) {
        return 0;
    }
    
    const sourceMap = {};
    for (let i = 0; i < s.length; i++) {
        sourceMap[s[i]] = (sourceMap[s[i]] || 0) + 1;
    }
    // 如果不包含全部三种字符, 则返回 - 1
    if (Object.keys(sourceMap).length < 3) {
        return -1;
    }
    // targetMap val 为 sourceMap val - k
    const targetMap = {};
    for (const [key, val] of Object.entries(sourceMap)) {
        targetMap[key] = val - k;
        // 考虑 abc, k = 2, targetMap 会有负数, 无法取到
        if (val - k < 0) {
            return -1;
        }
    }
    // match size 为 3
    // 初始的时候 window size 为 0, 全部都小于 targetMap, 一定符合题意
    const curMap = {};
    let match = 3;
    let maxWindowSize = 0;

    let left = 0;
    let right = 0;
    while (right < s.length) {
        while (match >= 3 && right < s.length) {
            // sourceMap 减少才能靠近 targetMap
            curMap[s[right]] = (curMap[s[right]] || 0) + 1;
            if ((curMap[s[right]] || 0) > targetMap[s[right]]) {
                match-- ;
                // right 已经被纳入区间了, 此时已经不符合了, 不用再 right++ 了
                // break;
                // 必须要 right++, 不然 s[right] 会永远不 match, 导致死循环
            }
            else {
                // window 最大的时机在这里, 此时 [left, right] 依然是符合题意的
                maxWindowSize = Math.max(maxWindowSize, right - left + 1);
            }
            right++;
        }

        // 跳出循环的瞬间, [left, right - 1] 不 match 的, 不 match 的字符一定是 s[right - 1]
        while (left <= right && match < 3) {
            // 缩小 left, 直到重新 s[right] match
            curMap[s[left]]--;
            if ((curMap[s[right - 1]] || 0) <= targetMap[s[right - 1]]) {
                match++;
                // left 已经被移出区间了, 所以不能 break 一定要 left++
            }
            left++;
        };

        // 此时 [left, right] 继续符合题意
    }

    return s.length - maxWindowSize;
};